package com.xinwei.leetcode.数组;

import com.sun.java.swing.plaf.windows.WindowsTextAreaUI;

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
public class _121_买卖股票的最佳时机 {
    // 暴力破解  leetcode提交结果  超出时间
    public int maxProfit(int[] prices) {
        Integer max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] - prices[i] > max) {
                    max = prices[j] - prices[i];
                }
            }
        }
        return max;
    }

    // 成功 但超出时间限制
    public static int maxProfit1(int[] prices) {
        if (prices.length == 1) return 0;
        Integer max = 0;
        Integer min = prices[0];
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] <= min) {
                min = prices[i];
                for (int j = i + 1; j < prices.length; j++) {
                    if (prices[j] < min) {
                        i = j - 1;
                        break;
                    }
                    if (prices[j] - min > max) {
                        max = prices[j] - min;
                    }
                }
            }

        }
        return max;
    }

    // 改进  :  3,2,6,5,0,3baocuo   报错原因：逻辑是每拿到一个最小值i，就会跑j，跑j时若有j比i小则直接让i跑到j，
    public static int maxProfit2(int[] prices) {
        if (prices.length == 1) return 0;
        Integer max = 0;
        Integer min = prices[0];
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] <= min) {
                min = prices[i];
                max = prices[i];
                for (int j = i + 1; j < prices.length; j++) {
                    if (prices[j] < min) {
                        i = j - 1;
                        break;
                    }
                    if (prices[j] > max) {
                        max = prices[j];
                    }
                }
            }

        }
        return max - min;
    }

    // 官解，动态规划
    public static int maxProfit3(int[] prices) {
        Integer min = Integer.MAX_VALUE; //用于记录最小值
        Integer maxProfit = 0; // 用于记录最大利润
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
                continue;
            }
            if (prices[i] - min > maxProfit) maxProfit = prices[i] - min;
        }
        return maxProfit;
    }


}
